package com.zj.leetcode.medium.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @program: algorithm
 * @description:
 * 寻找重复的子树
 * 652 find-duplicate-subtrees
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class FindDuplicateSubtrees{
    public static void main(String[] args) {
        Solution solution = new FindDuplicateSubtrees().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    class Solution {
        List<TreeNode> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            serialize(root);
            return res;
        }

        public String serialize(TreeNode root) {
            if (root == null) {
                return "#";
            }
            // 逗号隔开，明确每个节点的值，防止12 2 和 1 22 直接拼接看起来相同
            String str = serialize(root.left) + "," + serialize(root.right) + "," + root.val;
            int count = map.getOrDefault(str, 0);
            // 已经存在且第一次重复
            if (count == 1) {
                res.add(root);
            }
            map.put(str, count+1);
            return str;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
